COMMENT ⊗   VALID 00005 PAGES 
RECORD PAGE   DESCRIPTION
 00001 00001
 00002 00002	.<<  Title page >>
 00004 00003	.HD INTRODUCTION
 00007 00004	.HD STATEMENT OF PROBLEM
 00013 00005	Consider \5\6S\*↓[f=f\4\*\4%\*α]w↓o(f)\1 and the cycles of \4%\*α.
 00020 ENDMK
⊗;
.<<  Title page >>
.BEGIN CENTER
ENUMERATION OF THE GRAPHS OF MOLECULES

Larry Masinter
Computer Science Department
Stanford University
Stanford, California

May, 1973
.END
.GROUP SKIP 5
.BEGIN INDENT 6,6,6
ABSTRACT. Previously, enumerations of the number of equialence classes of
graphs with a given partitions have been given<<PARTHA:
PARTHASARATHY PAPER>↑,<<OTHER:
OTHER REFERENCE>.
These results are
extended to give enumerations for the number of equivalence classes of
connected multigraphs.
Connected multigraphs correspond directly with chemical molecules; thus
the enumeration can be applied to count the number of chemical isomers
constructable from a given set of atoms.
Bounds may be placed on the
multiplicity of each edge, corrsponding to restrictions on multiple bonds
in chemical structures.
.END
.
.EVERY FOOTING(,{PAGE},)
.
.SKIP TO COLUMN 1
.SPACE2;
.HD INTRODUCTION
A \2multi-graph\1 of order \5n\1 is the set \5N={1,...,n}\1 (called the
\2nodes\1 of the graph) together with a mapping \5f\1 from the set
\5E(n)={{i,j}|1≤i<j≤n}\1 to the set of non-negative integers \5I↑+\1.
Those \5eεE\1 for which \5f(e)≠0\1 are said to be \2edges\1 of the graph;
the \2multiplicity\1 of \5e\1 is \5f(e)\1. Also, if \5e={i,j}\1 then node
\5i\1 is said to be connected to node \5j\1 with multiplicity
\5f({i,j})\1. Multigraphs may be restricted to those whose edges have
maximum multiplicity \5k\1 by restricting the range of \5f\1 to be the
set of integers \5{0,1,...,k}\1. A \5k\2-multigraph\1 is thus an element
of \5k+1↑[E(n)]\1.

The \2degree\1 of a node \5nεN\1 is \5d(n)=\6S\*↓[m≠n]f({n,m})\1. The degree
is the total number of other nodes \5n\1 is connected to, with each
connection counted the appropriate multiplicity number of times.
The \2degree seqence\1 of a graph \5f\1 is defined to be the ordered
list \5ds(f)=(o↓1,o↓2,...)\1, where \5o↓1≤o↓2≤...≤o↓n\1, and
\5|{j:o↓j=k}|=|{l:d(l)=k}|\1. It is the sorted list of the degrees of
the nodes of \5f\1.

Given a set \5X\1, the \2symmetry group\1 on \5X\1, or \5S↓X\1, is defined
to be the set of all automorphisms from \5X\1 onto \5X\1.

Two graphs \5f\1, \5g\1 of order \5n\1 are said to be \2isomorphic\1 if there
exists a permutation \5αεS↓N\1 such that \5∀i,jεN f({i,j})=g({α(i),α(j)})\1.
This is written \5f\4↔\*g\1.

.GRAF Lemma
\5f\4↔\*g => ds(f) = ds(g).\1

Given a set \5F\1 and an equivalence relation \4↔\* on \5F\1, we define
the set of equivalence classes of \5F\1 under \4↔\*, \5F\1/\4↔\*, to be
\5{{fεF:f\4↔\*g} | gεF}\1.

.HD STATEMENT OF PROBLEM
Thus, the the problem is to find a generating function for the
number of equivalence classes of k-multigraphs with a given
degree sequence \5(o↓0,o↓1,o↓2,...)\1.

.GRAF Burnside lemma
Let \5E\1 be a set, \5G\1 a finite group with a mapping \5\4%\*:G→S↓E\1.

Let \5B\1 be a finite set, and \5\4#\*=B↑E\1.

Define the equivalence relation \4↔\* for \5f,gε\4#\*\1, such that \5f\4↔\*g\1
if there exists \5αεG\1 such that \5f=g\4⊗\*\4%\*(α)\1.

Let \5w\1 be a mapping \5w:\4#\*→\4@\*\1, where \4@\* is a field, such that
\5f\4↔\*g => w(f)=w(g)\1. We call \5w\1 the weight function.

For \5F\1 an equivalence class in \4#\*/\4↔\*, define \5W(F)\1 to be \5w(f)\1 for any \5fεF\1.

Then
.BEGIN NOFILL

\5\6S\*↓[↓[Fε\4#\*/\4↔\*]]W(F)

 = ↑[ 1 ]&↓[|G|]&--- \6S\*↓[αεG]\6S\*↓[↓[f=f\4⊗\*\4%\*α]]w(f).\1
.END
To apply the Bernside lemma to this problem,
it is necessary to devise a weight function such that two graphs with
the same degree sequence have the same weight and graphs with different
degree sequences have different weights. Further, to construct a generating
function for the number of graphs with given degree sequences, the degree
sequences should be reflected in the exponents of terms in the weight rather
than in the coefficient.

Thus, we define the weight function \5w↓o\1 on \5k↑[E(n)]\1 into the set of real
polynomials in \5u↓1,u↓2,...,u↓n\1 by:

\5w↓o(f)=\6P\*↓[↓[1≤i<j≤n]](u↓iu↓j)↑[f({i,j})]\1

The exponent of \5u↓i\1 in \5w↓o(f)\1 will be the degree of node \5i\1
in the graph \5(N,f)\1.
Unfortunately, \5ds(f)=ds(g)\1 (or even \5f\4↔\*g\1) does not imply \5w↓o(f)=w↓o(g)\1;
although \5f\1 and \5g\1 have the same degree sequence, the exponents may be permuted
among the \5u↓i\1.
It is necessary to apply a symmetrizing operator \4∂\*:

.GRAF Definition
For \5w\1 a function in \5u↓1, u↓2, ... u↓n,\1 define
.BEGIN NOFILL

\5\4∂\*(w)(u↓1,u↓2,...,u↓n)
    =↑[1 ]&↓[n!]&[--]\6S\*↓[αεS↓N]w(u↓[α↓1],u↓[α↓2],...,u↓[α↓n])\1

Note:
        1) \4∂\* is linear
        2) if \5w\1 is symmetric, then \5\4∂\*w=w\1;
           specifically, \5\4∂\*\4∂\*w=\4∂\*w\1 for any \5w\1.

The weight function w can now be defined by:
        for \5fεk↑E,  w(f)=\4∂\*w↓o(f)\1.
.END
This weight function satisfies our requirements:
If the degree sequence of \5f\1 is \5o↓1≤o↓2≤o↓3≤...o↓n\1, the weight of \5f\1
will be:
.BEGIN NOFILL

                \5\4∂\*u↓1↑[o1]u↓2↑[o2]...u↓n↑[on]\1
.END
Then, using the definition of \4↔\* given earlier, with
the representation of the group \5G=S↓N\1 by \5\4%\*(G), where
\5\4%\*:S↓N→S↓E by \4%\*(β){i,j}={β(i),β(j)}\1
we obtain:
.BEGIN NOFILL

\5\6S\*↓[↓[fε\4#\*/\4↔\*]]w(f)
        =↓[n!]&↑[1 ]&[--]\6S\*↓[αεS↓n]\6S\*↓[f=f\4⊗\*\4%\*α]w(f)
        =↓[n!]&↑[1 ]&[--] \4∂\*\6S\*↓[αεS↓n]\6S\*↓[f=f\4⊗\*\4%\*α]w↓o(f)\1
.END
Consider \5\6S\*↓[f=f\4⊗\*\4%\*α]w↓o(f)\1 and the cycles of \4%\*α.
\5f=f\4⊗\*\4%\*α <=> f\1 is constant on each cycle of \4%\*α.
For a given α, let \5M↓[α]\1 be the number of cycles of \4%\*α; for
\51≤r≤M↓[α]\1, let \5C↓r&↑α\1 be the set of edges (elements of \5E\1) in
the r-th cycle of \4%\*α, and
.       begin nofill

\5U↓r↑[α]=\6P\*↓[↓[{l,p}εC↓r]]u↓lu↓p\1

Then for \5f=f\4⊗\*\4%\*α\1,

\5w↓o(f)=\6P\*↓[i,j](u↓iu↓j)↑[f({i,j})]

     =\6P\*↓[1≤r≤M](U↓r&↑[α])↑[f(cycle r)]\1
.       end
Since each \5f=f\4⊗\*\4%\*α\1 can be specified by its value on the cycles
of \4%\*α, there is a 1-1 correspondence between such \5f\1 and
\5\6s\*ε{0,1,...,k}↑M\1, where \5k\1 is the maximum multiplicity (can be ∞),
by \5\6s\*(r)=f(cycle r).\1
In particular,
.       begin nofill

  \5V(α)=\6S\*↓[↓[f=f\4⊗\*\4%\*α]]w↓o(f)
        =\6S\*↓[↓\6s\*] \6P\*↓[↓[1≤r≤Mα]] (U↓r↑[α])↑[(r)]
        =\6P\*↓[↓[1≤r≤Mα]]↑[↑[1-(U↓r)↑k]]&↓[↓[1 - U↓r]]&[-------]
      (or \6P\*↓[↓[1≤rMα]]↑[↑[  1  ]]&↓[↓[1-U↓r]]&[-------] if k=∞)\1
.       end
Our generating function is now
.begin nofill
         \5↓[n!]&↑[1 ]&[--]\4∂\*\6S\*↓[αεS↓N]V(α).\1
.end continue
We wish to group the summation by those permutations α with cycle index
\5λ↓1+2λ↓2+...+nλ↓n=n\1 (\5λ↓i\1 is the number of \5i\1-cycles of α; note that
this is different from the number of various cycles of \4%\*α).
Let \5α\4⊗\*(λ↓1,λ↓2,...,λ↓n)\1 be the permutation obtained by filling in
the integers \51,...,n\1 into the slots in
.       begin nofill

  (.)(.)...(.)     (..)(..)(..)   ...   (.. ...)
   ----------   ----------       -----
   λ↓1 1-cycles  λ↓2 2-cycles ... λ↓n n-cycles
.       end
For \5\6s\*εS↓N, \6s\*α\4⊗\*\6s\*↑[-1]\1 has the same cycle structure as α; further, there
are exactly
.BEGIN NOFILL

\5Y(λ↓1,λ↓2,...,λ↓n)=\6P\*↓[1≤k≤n] (k↑[↑[λ]k]λ↓k!)\1
.END CONTINUE
such permutations. Thus,
.BEGIN NOFILL

\5\6S\*↓[αεS↓N]V(α)
      =\6S\*↓[λ↓1+...+λ↓n=n]↓[Y(\2)]&↑[  1  ]&[-----] \6S\*↓[↓[\6s\*εS↓N]]V(\6s\*\4⊗\*α↓[λ]\4⊗\*\6s\*↑[-1])\1
.END